/*
 * @lc app=leetcode.cn id=322 lang=cpp
 *
 * [322] 零钱兑换
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;


// @lc code=start
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();               // 记录硬币种类的数量
        vector<int> dp(amount + 1, -1);     // dp[i] 表示金额 i 需要的最少硬币数量        

        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                // 如果硬币面额小于需要的金额，则可以调用子问题
                if (i >= coin && dp[i - coin] != -1) {
                    dp[i] = (dp[i] == -1) ? dp[i - coin] + 1 : min(dp[i], dp[i - coin] + 1);
                }
            }
        }
   
        return dp[amount];
    }
};
// @lc code=end

